﻿//力扣：22. 括号生成
//链接：https://leetcode.cn/problems/generate-parentheses/description/


//方法：DFS

//算法原理：总结来说就是：有效的括号组合符合以下两个条件：
//1. 左括号的数量 = 右括号的数量(代码：只要 左括号数量 < 生成括号的对数(n)，就可以继续放置左括号)
//2. 从头开始（从左往右）的任意一个子串，左括号的数量 >= 右括号的数量（代码：只要 右括号数量 < 左括号数量，就可以继续放置右括号）
//
//详细解释如下（选读）：
//从左往右进⾏递归，在每个位置判断放置左右括号的可能性，若此时放置左括号合理，则放置左括号继续进⾏递归，右括号同理。
//⼀种判断括号是否合法的⽅法：从左往右遍历，左括号的数量始终⼤于等于右括号的数量，并且左括号的总数量与右括号的总数量相等。因此我们在递归时需要进⾏以下判断：
//1. 放⼊左括号时需判断此时左括号数量是否⼩于字符串总⻓度的⼀半（若左括号的数量⼤于等于字符串⻓度的⼀半时继续放置左括号，则左括号的总数量⼀定⼤于右括号的总数量）；
//2. 放⼊右括号时需判断此时右括号数量是否⼩于左括号数量。
//
//递归函数参数设置为当前状态的字符串⻓度以及当前状态的左括号数量，递归流程如下：
//1. 递归结束条件：当前状态字符串⻓度与 2 * n 相等，记录当前状态并返回；
//2. 若此时左括号数量⼩于字符串总⻓度的⼀半，则在当前状态的字符串末尾添加左括号并继续递归，递归结束撤销添加操作；
//3. 若此时右括号数量⼩于左括号数量（右括号数量可以由当前状态的字符串⻓度减去左括号数量求得），则在当前状态的字符串末尾添加右括号并递归，递归结束撤销添加操作；
class Solution
{
public:
    int left, right, count;             // left：左括号数量，right：右括号数量，count：括号对数
    vector<string> ret;                 // 存储最终的有效括号组合
    string path;                        // 当前括号组合路径

    // 深度优先搜索（DFS），递归生成括号组合
    void dfs()
    {
        if (right == count)
        {
            ret.push_back(path);        // 当右括号数量达到指定数量时，表示生成了一个完整的括号组合，记录当前的有效括号组合
            return;
        }

        // 若左括号数量小于括号对数，则可以继续添加左括号
        if (left < count)
        {
            path.push_back('('); left++;// 将左括号添加到当前路径，左括号数量增加（两句代码配套，这里放一起更方便展示）
            
            dfs();                      // 递归生成下一个括号

            path.pop_back(); left--;    // 回溯（“回溯现场”），移除最后一个括号，左括号数量减少（两句代码配套，这里放一起更方便展示）
        }

        // 若右括号数量小于左括号数量，则可以继续添加右括号
        if (right < left)
        {
            path.push_back(')');        // 添加右括号
            right++;                    // 右括号数量增加

            dfs();                      // 递归生成下一个括号

            path.pop_back();            // 回溯，移除最后一个括号
            right--;                    // 恢复右括号数量
        }
    }

    vector<string> generateParenthesis(int n)
    {
        count = n;                      // 初始化括号对数
        dfs();                          // 从初始状态开始递归生成括号组合
        return ret;                     // 返回所有生成的有效括号组合
    }
};